//给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 
//
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 
//
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 
//
// 
//
// 示例 1: 
//
// 
//输入：prices = [3,3,5,0,0,3,1,4]
//输出：6
//解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
//     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。 
//
// 示例 2： 
//
// 
//输入：prices = [1,2,3,4,5]
//输出：4
//解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
//     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
//     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
// 
//
// 示例 3： 
//
// 
//输入：prices = [7,6,4,3,1] 
//输出：0 
//解释：在这个情况下, 没有交易完成, 所以最大利润为 0。 
//
// 示例 4： 
//
// 
//输入：prices = [1]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= prices.length <= 105 
// 0 <= prices[i] <= 105 
// 
// Related Topics 数组 动态规划 
// 👍 948 👎 0

package com.cute.leetcode.editor.cn;
public class BestTimeToBuyAndSellStockIii {
    public static void main(String[] args) {
        new BestTimeToBuyAndSellStockIii().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 只有一个限制：最多进行两次交易，即可以交易的次数为0、1、2
         * 如何在所有的交易中金额最大的两次呢？--->定义一个状态
         * 定义状态方程dp[i][j][k]表示在区间[0,i]内，交易进行了j次，且状态为k时所拥有的现金数
         * j=0表示没有交易发生，j=1表示发生了一次交易，j=2表示发生了两次交易，0次交易没有实际意义
         * k为0表示不持股，k=1表示持股
         *
         * 规定：记录一次交易是在买入时进行记录的
         * 输出值：交易一次或交易两次不持股的收益最大值
         */
        public int maxProfit(int[] prices) {
            int len = prices.length;
            if ( len < 2 ) return 0;
            int[][][] dp = new int[len][3][2];
            //dp[0][0][0] = 0;//没买入不持股
            //dp[0][0][1] = 0;//这个状态不可能存在
            //dp[0][1][0] = 0;//第一天买入但是不持股，不可能存在
            dp[0][1][1] = -prices[0];//表示一次买入持有股票（第一天买入）
            //dp[0][2][0] = 0;//不可能存在

            //TODO 这个位置按照题解作者的意思是，当天内不允许多次交易（即不能浪费交易次数）
            // 所以第一天的时候这种状态不存在，需要设置为一个不能的值
            // 为什么不能设置为0：后边进行比较的时候会将 dp[i-1][2][1],dp[i-1][1][0]-prices[i] 进行比较
            // 如果初始化为0的话，可能会导致dp[i-1][1][0]-prices[i]无法取到，导致结果出错
            // 其实初始化只需要设置为 < -price[0] 的数就可以了
            /**
             * 有一种题解是允许当天多次交易的，即浪费交易次数
             * 那么在第一天的时候就可能出现[2][1]这种状态
             * 且此时的状态值就是-price[0]
             */
            dp[0][2][1] = Integer.MIN_VALUE;//两次买入且持股，不可能在第一天可能发生，但是不能初始化为0
            for (int i = 1; i < len ; i++) {
                //TODO 转移顺序先持股，再卖出
                //今天买入次数为1且持股：昨天买入次数为1且持股/昨天买入次数为0且不持股即今天是第一次买入
                dp[i][1][1] = Math.max(dp[i-1][1][1],-prices[i]);
                //今天买入次数为1且不持股：昨天买入次数为1且不持股/昨天买入次数为1且持股今天卖出
                dp[i][1][0] = Math.max(dp[i-1][1][0],dp[i-1][1][1]+prices[i]);
                //今天买入次数是2且持股：昨天买入次数是2且持股/昨天买入次数是1且不持股今天再买入一次
                dp[i][2][1] = Math.max(dp[i-1][2][1],dp[i-1][1][0]-prices[i]);
                //今天买入次数是2且不持股：昨天买入次数是2且持股今天卖出/昨天买入次数是2且不持股
                dp[i][2][0] = Math.max(dp[i-1][2][1]+prices[i],dp[i-1][2][0]);
            }
            return Math.max(dp[len-1][2][0],dp[len-1][1][0]);
        }

        /**
         * 二刷的时候也是这样想的，写出压缩数组的方法
         */
        public int maxProfit2(int[] prices) {
            int len = prices.length;
            //需要额外定义一个状态记录交易次数
            //第一个位置为天数；第二个为是否持股，0表示不持股，1表示持股；第三方位置为买入次数
            //注意买入次数只能从0向2推，以及自身推 即 0->(0,1) 1->(1,2) 2->2
            //可以压缩空间到常数阶
            int[][] pre = new int[2][3];
            int[][] cur = new int[2][3];
            pre[1][1] = -prices[0];
            pre[1][2] = -prices[0];
            for (int i = 1; i<len; i++){
                //今天卖出的话昨天必须持股
                cur[0][1] = Math.max(pre[0][1],pre[1][1] + prices[i]);
                cur[0][2] = Math.max(pre[0][2],pre[1][2] + prices[i]);
                //今天买入的话昨天必不能持股
                cur[1][1] = Math.max(pre[1][1],pre[0][0] - prices[i]);
                cur[1][2] = Math.max(pre[1][2],pre[0][1] - prices[i]);
                pre = cur;
            }
            //不浪费交易次数，所以返回买入次数为2的之中的最大值
            return Math.max(cur[0][2],cur[1][2]);
        }

        /**
         * 代码随想录的题解
         * 一天之内只能有5种状态
         * 0：表示当天不操作
         * 1：表示当前第一次买入的状态（并不是一定要买入，状态可以延用，后续同理）
         * 2：表示当天第一次卖出的状态
         * 3：表示当天第二次买入的状态
         * 4：表示当天第二次卖出的状态
         * 也可压缩空间到常数
         */
        public int maxProfit3(int[] prices) {
            int[][] dp = new int[prices.length][5];
            dp[0][1] = -prices[0];
            dp[0][3] = -prices[0];//表示不浪费交易次数
            for (int i = 1; i < prices.length ; i++) {
                //不操作的话就不管了
                dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
                dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]);
                dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i]);
                dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i]);
            }
            return dp[prices.length-1][4];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}